#[test]
fn test_next_permutation() {
    {
        let mut nums = vec![1, 2, 3, 4, 6, 5];
        next_permutation(&mut nums);
        assert_eq!(nums, vec![1, 2, 3, 5, 4, 6]);
    }

    {
        let mut nums = vec![1, 2, 3];
        next_permutation(&mut nums);
        assert_eq!(nums, vec![1, 3, 2]);
    }

    {
        let mut nums = vec![3, 2, 1];
        next_permutation(&mut nums);
        assert_eq!(nums, vec![1, 2, 3]);
    }

    {
        let mut nums = vec![1, 1, 5];
        next_permutation(&mut nums);
        assert_eq!(nums, vec![1, 5, 1]);
    }

    {
        let mut nums = vec![1];
        next_permutation(&mut nums);
        assert_eq!(nums, vec![1]);
    }
}
/*
31. 下一个排列
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。

示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]

示例 4：
输入：nums = [1]
输出：[1]

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100
*/
pub fn next_permutation(nums: &mut Vec<i32>) {
    let n = nums.len();
    for i in (0..n - 1).rev() {
        if nums[i] < nums[i + 1] {
            let mut swap_at = n - 1;
            while nums[i] >= nums[swap_at] {
                swap_at -= 1;
            }
            nums.swap(i, swap_at);
            nums[i + 1..].reverse();
            return;
        }
    }
    nums.reverse();
}
